/**
 * // Definition for a QuadTree node.
 * function _Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight) {
 *    this.val = val;
 *    this.isLeaf = isLeaf;
 *    this.topLeft = topLeft;
 *    this.topRight = topRight;
 *    this.bottomLeft = bottomLeft;
 *    this.bottomRight = bottomRight;
 * };
 */

/**
 * @param {number[][]} grid
 * @return {_Node}
 */
/* 
要解决建立四叉树的问题，我们可以通过递归的方式，将矩阵不断划分为四个子矩阵，直到子矩阵中的所有元素都相同，从而构建出四叉树的结构。

方法思路
递归划分矩阵：对于给定的矩阵区域，判断其中所有元素是否相同。如果相同，则创建一个叶子节点；
如果不同，则将矩阵划分为四个相等的子矩阵，递归构建每个子矩阵对应的四叉树节点，并将这些节点作为当前节点的四个子节点。
判断元素是否相同：通过遍历当前矩阵区域内的所有元素，检查它们是否都等于左上角的元素。如果有任何一个元素不同，则说明该区域需要进一步划分。
处理边界条件：当矩阵区域的大小为 1 时，该区域必然是一个叶子节点。
*/

var construct = function (grid) {
  // 递归辅助函数，根据矩阵的左上角坐标和大小构建四叉树
  const build = (row, col, size) => {
    // 如果区域大小为1，直接创建叶子节点
    if (size === 1) {
      return new _Node(grid[row][col] === 1, true, null, null, null, null);
    }

    // 检查当前区域内所有元素是否相同
    let isUniform = true;
    const value = grid[row][col];
    for (let i = row; i < row + size; i++) {
      for (let j = col; j < col + size; j++) {
        if (grid[i][j] !== value) {
          isUniform = false;
          break;
        }
      }
      if (!isUniform) break;
    }

    // 如果所有元素相同，创建叶子节点
    if (isUniform) {
      return new _Node(value === 1, true, null, null, null, null);
    }

    // 否则，划分成四个子区域，递归构建子节点
    const half = size / 2;
    const topLeft = build(row, col, half);
    const topRight = build(row, col + half, half);
    const bottomLeft = build(row + half, col, half);
    const bottomRight = build(row + half, col + half, half);

    // 创建当前非叶子节点，val可以为任意值（这里用true）
    return new _Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
  };

  // 从整个矩阵的左上角(0,0)开始，大小为grid.length
  return build(0, 0, grid.length);
};